package com.cdream.basic.algorithm.leetcode.dfs;

import java.util.Arrays;

/**
 * @author cdream
 * @date 6/7/21
 */
public class Question494 {
    private int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < target || (sum - target) % 2 != 0) {
            return 0;
        }
        int y = (sum - target) / 2;

        int[] dp = new int[y + 1];
        dp[0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = y; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i - 1]];
            }
        }
        return dp[y];
    }

    public int findTargetSumWays3(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < target || (sum - target) % 2 != 0) {
            return 0;
        }
        int y = (sum - target) / 2;

        int[][] dp = new int[nums.length + 1][y + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= y; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][y];
    }


    public int findTargetSumWays2(int[] nums, int target) {
        dfs(nums, 0, target, 0);
        return count;
    }

    private void dfs(int[] nums, int index, int target, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        dfs(nums, index + 1, target, sum + nums[index]);
        dfs(nums, index + 1, target, sum - nums[index]);
    }
}
